/**
 * @author LKQ
 * @date 2022/1/12 15:52
 * @description 利用行升序，列升序，那么从右上角或左下角开始遍历。时间复杂度 O(m + n)
 */
public class FormalSolution3 {
    public static void main(String[] args) {
        FormalSolution3 solution3 = new FormalSolution3();
        int[][] matrix = {{1,4,7,11,15}, {2,5,8,12,19}, {3,6,9,16,22}, {10,13,14,17,24}, {18,21,23,26,30}};
        solution3.searchMatrix(matrix, 5);
    }
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int x = 0, y = n - 1;
        while (x < m && y >= 0) {
            int t = matrix[x][y];
            if (t == target) {
                return true;
            } else if (t > target) {
                y--;
            } else {
                x++;
            }
        }

        return false;
    }
}
